This invention relates to computer systems having a plurality of resources which are utilized to varying degrees. More particularly, this invention relates to such a computer system in which the selection of resources depends on historical loading, and which provides a mechanism for handling a resource that has no history, either because the resource is new or because maintaining the history for all resources is too difficult or expensive.
Computer systems or networks typically have multiple resources (processors, data objects, memory devices, communications gateways, output devices, etc.). In many cases, the system must select a resource from a group of resources of a particular type. For example, a central processing unit ("CPU") in a multiprocessor system must be chosen to perform a task, a storage server in a computer network must be chosen to host a data object, a data item must be chosen to be evicted from a cache memory, etc. The goal in such cases is to make a selection that will result in the fastest or most efficient operation of the system or network. Frequently, such selections are made based on utilization statistics. Thus, for whatever type of resource is required, utilization statistics are examined and, most commonly, that resource of the required type, that in the recent past has had a utilization metric (e.g., rate or count) that is, depending on the nature of the task, either the lowest or highest utilization metric of all resources of that type, is selected. However, such a selection technique can lead to anomalous or unintended results in certain situations, particularly when a new resource, for which no usage statistics are available, is added to the group of resources.
For example, in the case of a computer system having multiple processors, the known selection technique for assignment of tasks to processors would result in the selection of the processor that is least busy. However, if a new processor is added to the system (or an existing processor that was offline returns to active status), that processor will, by definition, have the lowest utilization metric of any processor in the system. Therefore, for a time, all new tasks will be assigned to that processor. Because there is a lag in updating the utilization statistics, the new processor will, at least temporarily, be swamped. Ultimately, the statistics will reflect the high utilization, tasks will no longer be assigned to that processor, and the system will stabilize. In the meantime, however, system performance may be degraded.
As another example, in a computer system having a large number of processors and a large number of other resources, it may be desirable to locate each particular other resource at the same location as the processor that most frequently uses it (i.e., to "co-locate" the other resource with the processor), to reduce communication traffic and delay in the system. To determine which of the various processors that requests a particular other resource is the one that requests that resource most frequently, it may be impractical, particularly in a very large system, to keep statistics on every processor's utilization of every other resource. Therefore, instead, it is known to keep statistics on a group of processors that are the "best candidates" for co-location of a particular other resource thereat. When a new processor requests the other resource, it is a potential candidate and so is added to the group, replacing the candidate with the lowest number of "hits." However, the new processor is now the candidate with the lowest number of hits. Therefore, if a second new processor requests the same other resource, it will replace the first new processor in the list of candidates for co-location. One can envision a situation where two new processors become the most frequent users of a particular resource, but never get established on the list candidates for co-location because each continually replaces the other on the list.
In another example, a computer system may have a cache capable of holding a certain number of data objects that is less than the total number of data objects that may need to be cached. The goal would be to cache those objects most frequently used. The first time some new object is used, it is not known whether it will become frequently used or not. Therefore, it is typically inserted into the cache, and its utilization is monitored. However, the utilization metric is "1" (i.e., one use) the first time the object is placed in the cache, which by definition is the lowest utilization metric for any object in the cache (except perhaps for other objects with the same utilization metric). If a second new object arrives, it will be inserted in the cache and, if the cache is full, the object with the lowest utilization metric will be evicted from the cache. Normally, that would be the previous "new" object. Even if the previous new object is extremely popular, it may never get a chance to be established in the cache, or it may not get established until much later than it should, because it will be caught in a cycle of being inserted in the cache and then evicted in favor of other new objects.
It is clear, then, that selection mechanisms that rely on historical utilization data may not handle well the situation where a new resource, for which there are no historical data, is added.
It would be desirable to be able to provide a computer system or network in which selection of resources depends on historical loading, but which provides a mechanism for handling a resource that has no history, either because it is new or because its history has not been maintained.